package d_ch12.dijkstra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

import c_ch11.kruskal.WeightedGraph_try;
//一次通过！！ 基于了自己的总结，并没有看基于pq的答案；
public class Dijkstra_final_try { //O(ElogE)  如果使用索引堆，可以优化为O(ElogV；   实际应用中对于大部分图其实都不是稠密图，所以使用pq优势很大；
	
	private int s;
	private boolean[] fixed;
	private int[] dis; // 留下来的值 和 已经定的值;		（不断更新逼近最终答案，一般这样的变量都是这个语意）
	private WeightedGraph_try g;
	private int[] pre;  //留下来的值 和 已经定下来的值; 		所有边都会访问一遍，所以只要保证更新即可；
	
	public Dijkstra_final_try(WeightedGraph_try g, int s) {
		this.g = g;
		this.s = s;
		
		fixed = new boolean[g.getV()];
		
		dis = new int[g.getV()];
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[s] = 0;
		
		pre = new int[g.getV()];
		Arrays.fill(pre, -1);
		pre[s] = s;
		
		int cur = s;  //定下来的顶点，s已经定了，就没必要进入pq了，pq就是为了找该定的点的；顶点s留下来的全是正无穷 所以这一轮留下的就是[空]；
		PriorityQueue<Pair> pq = new PriorityQueue<>(); //为了方便找最小值的顶点而设，语意是留下来的值；因为我们选最小值只关心留下来的；有些顶点的dis是无穷大，没必要加入。。不可能选中；
		OUT:while(true) {
			fixed[cur] = true; //每一个顶点都会被定下来，所以下边的for循环把所有边访问了一遍；
			
			//在cur的基础上多走一步 和留下来的dis比较 择小更新；
			for (int i : g.adj(cur)) { 
				if(!fixed[i] && dis[cur]+g.weight(cur, i) < dis[i]) {
					dis[i] = dis[cur]+g.weight(cur, i);
					pq.add(new Pair(i, dis[i]));     //入pq就表示和留下来的进行比较，如果是小的 自然会排的靠前，就相当于更新了，不过会带来二次选中的问题：老值还在队里排着，不过我们可以在poll的时候做判断；
					pre[i] = cur;					//所有顶点过一遍，所有边过一遍
				}		//pre在这里维护 pre跟着dis更新就好了，因为所有边都会被访问，所以只要保证在该更新时更新就好了；
			}
			
			while(!pq.isEmpty()) { 			//这样写和改进前的思路一致，改动最小，思路最清晰；如果追求代码简短，用下边注释掉的几行也可以；
				int min = pq.poll().vertex;  //外层while和这个while迭代的次数是一样的，pq为空的时候就break了，所以不论是找次短值还是上边的fore更新都是最多不超过执行pq容量次，而每个有效顶点都会且仅会fore一次，所以pq最多E个元素不管重复的有多少，所以整体最多是Elog(E)级别（E是s所在连通分支的E，如果图不连通的话）;
				if( !fixed[min] ) {
					cur = min;
					continue OUT;
				}
				else
					continue;
			}			
			
			break;  //执行到这里说明全部都定了；
			
//			if(!pq.isEmpty())                //其实这里不判断二次选中也没事，因为二次选中后上边的逻辑都进不去；但是这里判断一下效率高一点点，因为上边进入adj后需要判断临边数量次，这里只需要一次；
//				cur = pq.poll().vertex;
//			else
//				break;			但不可以写成：!pq.isEmpty() ? cur = pq.poll().vertex : break; 因为三目元算符是选择性return的，x = a ?b:c; bc都得是表达式，可以return才行；	
		}
		
	}
	
	private class Pair implements Comparable<Pair>{
		public int vertex;
		public int dis;
		
		public Pair(int vertex, int dis) {
			super();
			this.vertex = vertex;
			this.dis = dis;
		}

		@Override
		public String toString() {
			return "[v=" + vertex + ", dis=" + dis + "]";
		}

		@Override
		public int compareTo(Pair o) {
			return this.dis - o.dis;
		}
		
	}
	
    public int disTo(int v){   //可能不连通 会返回无穷
        g.validateVertex(v);
        return dis[v];
    }
	
    public Iterable<Integer> getPath(int target) {
		g.validateVertex(target);
		ArrayList<Integer> ret = new ArrayList<>();
		if(!isConnectedTo(target)) return ret;   //这里又漏了，在写任何方法的时候一定要先想想特殊情况啊！
		
		int cur = target;
		while(cur != s) {
			ret.add(cur);
			cur = pre[cur];
		}
		ret.add(s);
		
		Collections.reverse(ret);
		return ret;
	}

    private boolean isConnectedTo(int target) {
    	g.validateVertex(target);
//		return dis[target] != Integer.MAX_VALUE;   测试过了 二者都可以，是等价的；
		return fixed[target];
	}
    
	static public void main(String[] args){

        WeightedGraph_try g = new WeightedGraph_try("g_ch12.txt");
        Dijkstra_final_try dij = new Dijkstra_final_try(g, 0);
        for(int v = 0; v < g.getV(); v ++)
            System.out.print(dij.disTo(v) + " ");
       
        System.out.println();
        
        for(int v = 0; v < g.getV(); v ++)
        	System.out.println("0-"+v+":"+dij.getPath(v));
    }
}
